// 358. K 距离间隔重排字符串
// vip会员
//输入: s = "aabbcc", k = 3
//输出: "abcabc"
//解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。
//示例 2:
//输入: s = "aaabc", k = 3
//输出: ""
//解释: 没有办法找到可能的重排结果。
//示例 3:
//输入: s = "aaadbbcc", k = 2
//输出: "abacabcd"
//解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

#include <bits/stdc++.h>
using namespace std;

struct MyChar{
  int ch = 0;
  int cnt = 0;
};
class Solution {
public:
  string CombineChars(string input, int interval) {
    if (interval<2) {
      return input;
    }
    map<char,int> mpChar;
    for (auto c : input) {
      mpChar[c]++;
    }
    auto cmp = [](MyChar& a, MyChar& b) {return a.cnt < b.cnt;};
    priority_queue<MyChar, vector<MyChar>, decltype (cmp)> mqChar(cmp);
    for (auto chr : mpChar) {
      mqChar.push({chr.first, chr.second});
    }
    queue<MyChar> quTemp;
    string ans;
    while(!mqChar.empty()) {
      auto chr = mqChar.top(); mqChar.pop();
      ans += chr.ch;
      chr.cnt--;
      quTemp.push(chr);
      if (quTemp.size()>=interval) {
        auto chr = quTemp.front(); quTemp.pop();
        if (chr.cnt) {
          mqChar.push(chr);
        }
      }
    }
    return input.length() == ans.length() ? ans : "";
  }
};
